package Class021;

import Class004.BasicSorts;
import Utils.ArrayUtils;

import java.util.Arrays;

public class Merge {
    public static void main(String[] args) {
        test();
    }

    public static void myMerge(int[] arr, boolean recursion) {
        if (recursion) mergeSort(arr, 0, arr.length - 1);
        else mergeIter(arr);
    }

    public static void merge(int[] arr, int l, int r, int mid) {
        int[] help = new int[r - l + 1];
        int lp = l, rp = mid + 1, index = 0;
        while (lp <= mid && rp <= r) {
            help[index++] = arr[lp] <= arr[rp] ? arr[lp++] : arr[rp++];
        }
        while (lp <= mid) {
            help[index++] = arr[lp++];
        }
        while (rp <= r) {
            help[index++] = arr[rp++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l == r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, r, mid);
    }

    public static void mergeIter(int[] arr) {
        int group = 1; //merge group
        int N = arr.length;
        while (group < N) {
            //while one part < N, means there is at least two part exist needing merge.
            for (int l = 0, m, r; l < N; l += (group << 1)) {
                //l stands for the left edge of a group.
                //l + group means the rp in merge(arr, l, r, m)
                //so if rp >= N, means there is no right part.
                if (l + group >= N) break;

                //if there exists right part, it does not mean there is enough num in right part.
                r = Math.min(l + (group << 1) - 1, N - 1);
                m = l + group - 1;
                merge(arr, l, r, m);
            }
            if (group >= (N >> 1)) break; //avoid exceeding.
            group <<= 1;
        }
    }

    public static void test() {
        int time = 10;
        int amount = 10000, max = 100;
        int errTime = 0;
        System.out.println("Correctness Test:");
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            int[] m = Arrays.copyOf(base, base.length);
            int[] b = Arrays.copyOf(base, base.length);
//            myMerge(m);
            mergeIter(m);
            BasicSorts.bubbleSort(b);
            if (!ArrayUtils.judge(b, m)) {
                System.out.println(Arrays.toString(base));
                System.out.println("Should be:");
                System.out.println(Arrays.toString(b));
                System.out.println("Wrong answer:");
                System.out.println(Arrays.toString(m));
                errTime++;
            }
        }
        if (errTime == 0) {
            System.out.println("All clear.");
        } else {
            System.out.println("Errors:" + errTime + "/" + time);
            System.out.println("Accuracy:" + (time - errTime) * 1.0 / time);
            return;
        }

        System.out.println("Time test:");
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            BasicSorts.bubbleSort(base);
        }
        e = System.currentTimeMillis();
        System.out.println("Bubble:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            myMerge(base, true);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Rec):" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            myMerge(base, false);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Ite):" + (e - s) + "ms");
    }
}
